package Algorithm.StackAndQueue;

import java.util.Stack;

/**
 * @Author cj
 * @Date 2021/11/10 19:56
 */
public class maxRecSize {

    public static int maxRecSize1(int[][] map) {
        if (map == null || map.length == 0 || map[0].length == 0) {
            return 0;
        }
        int[] height = new int[map[0].length];
        int res = 0;
        int i = 0;
        for (int j = 0; j < map.length; j++) {
            // 求每层height数组
            height[j] = map[i][j] == 0 ? 0 : map[i][j] + 1;
            // 求每层为底的最大矩阵面积
            res = Math.max(res, maxRecFromBottom(height));
            i++;
        }
        return res;
    }

    // 单调栈思路
    public static int maxRecFromBottom(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
        int res = 0;
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] <= height[stack.peek()]) {
                // 出栈，计算
                int tmp = stack.pop();
                res = Math.max(res,
                        stack.isEmpty() ? (i - (-1) - 1) * height[tmp] : (i - stack.peek() - 1) * height[tmp]);
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            int tmp = stack.pop();
            if (!stack.isEmpty()) {
                // 计算
                res = Math.max(res, (height.length - stack.peek() - 1) * height[tmp]);
            } else {
                res = Math.max(res, (height.length - (-1) - 1) * height[tmp]);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[][] map = {{1,0,1,1},
                {1,1,1,1},
                {1,1,1,0}};
        System.out.println(maxRecSize1(map));
    }
}
